import heapq
class Solution(object):
    def kSmallestPairs(self, nums1, nums2, k):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :type k: int
        :rtype: List[List[int]]
        """
        n1 = len(nums1)
        n2 = len(nums2)
        count = 0
        stack = [[nums1[i] + nums2[0], i, 0] for i in range(n1)]
        out = []
        while count < k and stack:
            node = heapq.heappop(stack)
            out.append([nums1[node[1]], nums2[node[2]]])
            if node[2] + 1 < n2:
                j = node[2] + 1
                heapq.heappush(stack, [nums1[node[1]] + nums2[j], node[1], j])
            count += 1
        return out



data = Solution()
nums1 = [1, 1, 2]
nums2 = [1, 2, 3]
k = 2
print(data.kSmallestPairs(nums1, nums2, k))
